package org.lyc.lanqiao.bank;

import java.util.Scanner;

/**
 * K倍区间
 * https://www.lanqiao.cn/problems/97/learning/?page=1&first_category_id=1&second_category_id=3&difficulty=20&contain_answer=true&sort=problem_id&asc=1
 * 给定长度为N的序列, 如果其中一段连续序列之和是K的倍数, 那么我们就称这个区间为K倍区间, 求出给定区间的K倍序列的个数, 要求时间复杂度为 O(n)
 * 第一行输入两个整数 N 和 K, 剩余N行输入完整序列
 * 输入样例:
 * 5 2
 * 1
 * 2
 * 3
 * 4
 * 5
 * 输出样例:
 * 6
 *
 * @author Liu Yicong
 * @date 2024/1/27
 */
public class EKFoldInterval {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] seq = new int[n];
		for (int i = 0; i < n; i++) {
			seq[i] = sc.nextInt();
		}
		basic(n, seq, k);
		prefixSum(n, seq, k);
		sameMod(n, seq, k);
	}

	/**
	 * 基础解法->暴力求解
	 *
	 * @param n   序列长度
	 * @param k   k值
	 * @param seq 初始化序列
	 */
	private static void basic(int n, int[] seq, int k) {
		int result = 0;
		for (int i = 0; i < n; i++) {
			int sum = 0;
			for (int j = i; j < n; j++) {
				sum += seq[j];
				if (sum % k == 0) {
					result++;
				}
			}
		}
		System.out.println(result);
	}

	/**
	 * 前缀和求解
	 * 对于求类似连续子区间的问题可以考虑使用前缀和, 即ai项为前i项和. 判断其ai到aj的连续子区间是否是K的整数倍, 用ai-aj即可.
	 * 前缀和可以避免频繁地计算相同的加法.
	 * 如:
	 * seq = [1 2 3 4 5]
	 * prefixSum = [0 1 3 6 10 15]
	 * 那么a2到a4这个子区间之和为9, 等价于prefixSum[4]-prefixSum[1]=9
	 * a1到a5之和即为a5=12, 可用prefixSum[5]-prefixSum[0]=15, prefixSum[0]恒为0以方便计算
	 *
	 * @param n   序列长度
	 * @param k   k值
	 * @param seq 初始化序列
	 */
	private static void prefixSum(int n, int[] seq, int k) {
		int[] ps = new int[n + 1]; //prefixSum 前缀和数组
		int result = 0;
		//遍历求前缀和
		ps[0] = 0;
		for (int i = 1; i <= n; i++) {
			ps[i] = ps[i - 1] + seq[i - 1];
		}
		for (int i = 1; i <= n; i++) {
			for (int j = i; j <= n; j++) {
				if ((ps[j] - ps[i - 1]) % k == 0) {
					result++;
				}
			}
		}
		System.out.println(result);
	}

	/**
	 * 同余统计
	 * 根据之前的前缀和我们可以求出前i项的和Si, 而如果Si和Sj拥有相同余数, 那么ai到aj一定是k的整数倍序列
	 * 如:
	 * prefixSum = [0 1 3 6 10 15] 对所有数取2的余数为
	 * modCount = [0 1 1 0 0 1]
	 * 那么a1到a2 a2到a5 a1到a5 必定是k的整数倍区间
	 * 因此, 只需要统计0~k这k+1个不同余数出现的次数即可统计出所有子区间
	 */
	private static void sameMod(int n, int[] seq, int k) {
		int[] ps = new int[n + 1]; //prefixSum 前缀和数组
		int[] mc = new int[k]; //modCount用于统计不同余数出现的次数, mc[1]表示prefixSum%k=1出现的次数. 注意数组的初始化值均为0
		int result = 0;
		//遍历求前缀和
		ps[0] = 0;
		mc[0] = 1;
		for (int i = 1; i <= n; i++) {
			ps[i] = ps[i - 1] + seq[i - 1];
			int remainder = ps[i] % k; //前缀和的余数
			mc[remainder]++;
		}
		for (int i = 0; i < k; i++) {
			int count = mc[i];
			result += count * (count - 1) / 2;
		}
		System.out.println(result);
	}
}
